package dataS.SortMethod;

//希尔排序
public class ShellSort {
    public static void main(String[] args) {
        int[] a = new int[]{9,8,7,6,10,1,2};
        shellSort2(a);
        for (int i : a) {
            System.out.print(i+" ");
        }
        //将待排序数组按照间隔分成若干个小组，然后对每个小组进行插入排序，此时整个数组部分有序，然后缩小增量再次分组再次排序，最后增量为1进行最后一次整体的插入排序

    }
    public static void shellSort(int []array){
        //初始化一个间隔
        int h=1;
        //计算最大间隔
        while (h<array.length/3){
            h=h*3+1;
        }
        while(h>0){
            //进行插入排序
            for(int i=h; i<array.length; i++){
                int temp = array[i];//保存每次需要插入的那个数
                int j;
                for(j=i; j>h-1&&array[j-h]>temp; j=j-h){
                    array[j] = array[j-h];//吧大于需要插入的数往后移动。最后不大于temp的数就空出来j
                }
                array[j] = temp;//将需要插入的数放入这个位置
            }
            //减小间隔
            h=(h-1)/3;
        }

    }
    public static void shellSort2(int nums[]){
        int n=nums.length;
        for(int gap=n/2;gap>0;gap/=2){
            for(int i=gap;i<n;i++){//当前增量下的组数
                insert2(nums,gap,i);
            }
        }

    }
    public static void insert(int nums[],int gap,int i){//将arr[i]正确插入所在分组
        int temp=nums[i];
        int j;
        for(j=i-gap;j>=0&&nums[j]>temp;j-=gap){
            nums[j+gap]=nums[j];
        }
        nums[j+gap]=temp;
    }
    public static void insert2(int nums[],int gap,int i){//将arr[i]正确插入所在分组
        int temp=nums[i];
        int j=i-gap;
        while(j>=0&&nums[j]>temp){
            nums[j+gap]=nums[j];
            j-=gap;
        }
        //循环执行完，j所指元素小于temp,那么temp的插入位置即j+gap
        nums[j+gap]=temp;
    }
}
